package bintree.LeetCode;
//236. 二叉树的最近公共祖先
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

import java.util.Deque;
import java.util.LinkedList;

/**
 * 思路一：笨方法，设计一个子方法，用来判断该树里面是否存在指定节点。
 * 当一个节点都满足包括 p，q 那就是公共祖先。
 * 把祖先一个个的存入栈中，最后一位公共祖先就是最近的祖先。
 */
//public class Num236_lowestCommonAncestor {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null){
//            return null;
//        }
//        Deque<TreeNode> ret = new LinkedList<>();//保存公共祖先
//
//        Deque<TreeNode> stack = new LinkedList<>();//用于排查节点
//        stack.push(root);
//        while(!stack.isEmpty()){
//
//            TreeNode cur = stack.pop();//弹出
//            if(lowest_pd(cur,p) && lowest_pd(cur,q)){
//                //说明包含,说祖先
//                ret.push(cur);
//            }
//            //把这个节点的左右子树压入栈一个个排查
//            if(cur.left != null){
//                stack.push(cur.left);
//            }
//            if(cur.right != null){
//                stack.push(cur.right);
//            }
//
//        }
//        return ret.pop();
//    }
//
//    /**
//     * 给你一个根节点和要寻找的节点值，判断该树中是否包含该节点。
//     */
//    public boolean lowest_pd(TreeNode root, TreeNode tmp){
//        if(root == null && tmp == null){
//            return true;
//        }
//        if(tmp == null){
//            return true;
//        }
//        if(root == null){
//            return false;
//        }
//        //节点都不为空
//        //用栈来循环，前序遍历
//        Deque<TreeNode> stack = new LinkedList<>();
//        stack.push(root);
//        while(!stack.isEmpty()){
//
//            TreeNode cur = stack.pop();//弹出
//            if(cur.val == tmp.val){
//                return true;//说明包含
//            }
//            //把这个节点的左右子树压入栈一个个排查
//            if(cur.left != null){
//                stack.push(cur.left);
//            }
//            if(cur.right != null){
//                stack.push(cur.right);
//            }
//
//        }
//        //到现在都还没找到，说明不存在
//        return false;
//    }
//
//}


/**
 * 思路二：利用找最近祖先的规律。最近祖先必定满足：在根，在左，在右。的其中两个
 *  后续遍历的方法。 注释：只有最近祖先才满足这个条件，其他祖先都没有。
 */
//注释：递归展开图在5.15 二叉树四里写了。1.01小时
public class Num236_lowestCommonAncestor {
    //最近公共祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //从树中每一个节点开始遍历找 p和 q这两个节点
        findNode(root,p,q);
        return lca;
    }

    /**
     * 从当前根节点出发，能否到找p或者q，找到一个就返回 return true
     */
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return false;
        }
        //返回1说明，此刻从左子树中至少找到了一个节点
        int left = findNode(root.left, p, q) ? 1 : 0;

        //返回1说明，此刻从右子树中至少找到了一个节点
        int right = findNode(root.right, p, q) ? 1 : 0;

        //返回1说明，此刻 根 节点就是
        int mid = (root == q || root == p) ? 1 : 0;

        //判断是否需要更新祖先节点
        if((left + right + mid) == 2){
            lca = root;
        }

        //大于0，说明在这个树中至少找到了一个节点
        return (left + right + mid) > 0;
    }

}
